package LeetCode;

import java.util.Arrays;

public class Code31_nextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0){
            return;
        }
        // 从后往前找第一个逆序的数
        int flag = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i - 1 >= 0 && nums[i-1] < nums[i]){
                flag = i - 1;
                break;
            }
        }
        // 如果没有，相当于54321要变成12345
        if (flag == nums.length - 1){
            int l = 0;
            int r = nums.length - 1;
            while (l < r){
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
        } else {
            // 从前往后找一个比flag大的最小数
            int greaterNum = Integer.MAX_VALUE;
            int greaterNum_index = flag;
            for (int i = flag; i < nums.length; i++) {
                if (nums[i] > nums[flag]){
                    greaterNum_index = nums[i] < greaterNum ? i : greaterNum_index;
                    greaterNum = Math.min(greaterNum, nums[i]);
                }
            }
            if (greaterNum_index != flag){
                // 交换
                int temp = nums[flag];
                nums[flag] = nums[greaterNum_index];
                nums[greaterNum_index] = temp;
            }
            Arrays.sort(nums, flag+1, nums.length);
        }
    }

    public static void main(String[] args) {
        Code31_nextPermutation nextPermutation = new Code31_nextPermutation();
//        int[] nums = {1,2,3};
//        int[] nums = {3,2,1};
        int[] nums = {1,1,5};
        nextPermutation.nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }
}
